package com.yan_jiu_sheng.LeetCodeHot100.AC;

import java.util.HashMap;

/**
 * https://leetcode.cn/problems/majority-element/?envType=study-plan-v2&envId=top-100-liked
 * 自我AC
 *
 * @author yulongtian
 * @create 2024-07-23 16:36
 */
public class Test86 {
    public static void main(String[] args) {
        int[] nums = {3, 3, 4};
        System.out.println(new Test86().majorityElement(nums));
    }

    /*
    进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
    想不出来
    Boyer-Moore 投票算法
     */
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = nums[0];

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }

        return candidate;
    }

    /*
    思路1：基数排序 思路正确    但内存超过限制
    思路2：哈希表存储 思路正确  通过测试    但并不是最优
     */
    public int majorityElement_my(int[] nums) {
//        int offset = 1000000000;
//        int[] buckets = new int[2 * offset + 1];
//        for (int i = 0; i < nums.length; i++) {
//            buckets[nums[i] + offset]++;
//        }
//        int max_num = Integer.MIN_VALUE;
//        int max_index = -1;
//        for (int i = 0; i < buckets.length; i++) {
//            if (buckets[i] > max_num) {
//                max_num = buckets[i];
//                max_index = i;
//            }
//        }
//
//        return max_index - offset;
        HashMap<Integer, Integer> map = new HashMap<>();
        int max_num = nums[0];
        int max_count = Integer.MIN_VALUE;
        for (int num : nums) {
            int temp = map.getOrDefault(num, 0) + 1;
            map.put(num, temp);
            if (temp > max_count) {
                max_num = num;
                max_count = temp;
            }
        }
        return max_num;
    }

}
